package woa.tree.binary;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉树的序列化与反序列化
 * 序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
 * 请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
 * 提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
 *
 * @author wangpeng
 * @date 2021/12/13
 */
public class Codec {

    public static String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }
        StringBuilder rs = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur == null) {
                rs.append("null").append(",");
                continue;
            }
            rs.append(cur.val).append(",");
            queue.offer(cur.left);
            queue.offer(cur.right);

        }
        return rs.toString();
    }

    public static TreeNode deserialize(String data) {
        if ("".equals(data)) {
            return null;
        }
        String[] nodes = data.split(",");
        TreeNode root = new TreeNode(Integer.valueOf(nodes[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        for (int i = 0; i < nodes.length; i++) {
            if (queue.isEmpty()) {
                break;
            }
            TreeNode cur = queue.poll();
            String leftStr = nodes[2 * i + 1];
            if (!"null".equals(leftStr)) {
                TreeNode left = new TreeNode(Integer.valueOf(leftStr));
                cur.left = left;
                queue.offer(left);
            }
            String rightStr = nodes[2 * i + 2];
            if (!"null".equals(rightStr)) {
                TreeNode right = new TreeNode(Integer.valueOf(rightStr));
                cur.right = right;
                queue.offer(right);
            }
        }
        return root;
    }

    public static void main(String[] args) {
//        TreeNode root = new TreeNode(1);
//        root.left = new TreeNode(2, null, new TreeNode(4));
//        root.right = new TreeNode(3, new TreeNode(5), null);
//        System.out.println(serialize(root));
        String data = "1,2,3,null,4,5,null,null,null,null,null,";
        deserialize(data);
    }
}
